package com.copa.l78;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author copa
 * @createDate 2022-05-17 17:07
 * @function 回溯法（广度优先遍历）
 */
public class Test3 {

    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        // 这里是按照当前长度进行遍历的
        for (int i = 0; i <= nums.length; i++) {
            backTracking(nums, result, i, 0, new ArrayList<>());
        }
        return result;
    }

    /**
     *
     * @param nums
     * @param result
     * @param length 当前长度
     * @param startIndex
     * @param tempList
     */
    private void backTracking(int[] nums, List<List<Integer>> result, int length, int startIndex, ArrayList<Integer> tempList) {
        if (length == tempList.size()) {
            // 如果此时tempList的长度跟当前长度一样，则加入结果集
            result.add(new ArrayList<>(tempList));
            return;
        }
        // 这里是遍历nums里的元素，不过tempList所能容纳的长度受到当前长度的限制
        for (int i = startIndex; i < nums.length; i++) {
            tempList.add(nums[i]);
            backTracking(nums, result, length, i + 1, tempList);
            tempList.remove(tempList.size() - 1);
        }
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1,2,3};
        List<List<Integer>> result = new Test3().subsets(nums);
        for (List<Integer> list : result) {
            System.out.println(Arrays.toString(list.toArray()));
        }
    }
}
